UVa/10482 - The candyman can/10482.3.cpp

   1 /*
   2   Problem: 10482 - The Candyman can
   3   (UVa Online Judge)
   4
   5   Andrés Mejía-Posada
   6
   7   ¡Accepted!
   8  */
   9 #include <iostream>
  10 #include <vector>
  11 #include <algorithm>
  12 using namespace std;
  13
  14 const int SIZE = 40, MAXN = 32;
  15
  16 /*
  17   dp[i][a][b] = verdadero si puedo repartir las primeras
  18   i monedas en tres grupos tales que el grupo con mayor peso
  19   tenga a unidades más que el grupo con menos peso & el grupo
  20   de la mitad tenga b unidades más que el grupo con menos peso
  21  */
  22 bool dp[MAXN][SIZE+1][SIZE+1];
  23
  24 int main(){
  25   int Casos;
  26   cin >> Casos;
  27   for (int C=1; C<=Casos; C++){
  28     int n, sum = 0;
  29     cin >> n;
  30     vector<int> w(n);
  31     for (int i=0; i<n; ++i){
  32       cin >> w[i];
  33       sum += w[i];
  34     }
  35
  36     sum = min(sum, SIZE);
  37
  38     for (int i=0; i<n; ++i)
  39       for (int a=0; a<=sum; ++a)
  40         for (int b=0; b<=sum; ++b)
  41           dp[i][a][b] = false;
  42
  43     cout << "Case " << C << ": ";
  44     //cout << "Sum: " << sum << endl;
  45
  46
  47     dp[0][w[0]][0] = true;
  48     for (int i=0; i<n-1; ++i)
  49       for (int a=0; a<=sum; ++a)
  50         for (int b=0; b<=sum; ++b)
  51           if (dp[i][a][b])
  52             for (int j=0; j<3; ++j){
  53               vector<int> t(3);
  54               t[0] = a, t[1] = b, t[2] = 0;
  55               t[j] += w[i+1];
  56               sort(t.begin(), t.end());
  57               if (t[2] - t[0] <= sum){
  58                 dp[i+1][t[2] - t[0]][t[1] - t[0]] = true;
  59               }
  60             }
  61
  62     int answer = -1;
  63     for (int a=0; a<=sum && answer == -1; ++a)
  64       for (int b=0; b<=a && answer == -1; ++b)
  65         if (dp[n-1][a][b]){
  66           answer = a;
  67         }
  68
  69     cout << answer << endl;
  70     if (answer == -1) while (true) cout << "error ";
  71
  72   }
  73   return 0;
  74 }
  75
  76